package _dp_base;

public class No265 {
    private int[][] costs;
    private int[][] cache;
    private int k;

    /**
     * 1. 递归
     */
    public int minCostII1(int[][] costs) {
        this.costs = costs;
        int n = costs.length;
        k = costs[0].length;
        cache = new int[n][k];

        int answer = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            answer = Math.min(answer, dfs(n - 1, j));
        }
        return answer;
    }

    private int dfs(int i, int j) {
        if (i == 0) return costs[i][j];
        else if (cache[i][j] != 0) return cache[i][j];
        else return cache[i][j] = bfs(i, j) + costs[i][j];
    }

    private int bfs(int i, int j) {
        int minVal = Integer.MAX_VALUE;
        for (int x = 0; x < k; x++) if (x != j) minVal = Math.min(minVal, dfs(i - 1, x));
        return minVal;
    }

    /**
     * 2. 迭代
     */
    public int minCostII2(int[][] costs) {
        int n = costs.length;
        k = costs[0].length;

        int[][] f = new int[n][k];
        System.arraycopy(costs[0], 0, f[0], 0, k);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                f[i][j] = bfs(i, j, f) + costs[i][j];
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            answer = Math.min(answer, f[n - 1][j]);
        }
        return answer;
    }

    private int bfs(int i, int j, int[][] f) {
        int minVal = Integer.MAX_VALUE;
        for (int x = 0; x < k; x++) if (x != j) minVal = Math.min(minVal, f[i - 1][x]);
        return minVal;
    }
}
